package solution;

/**
 * <a href="https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c?tpId=188&&tqId=38555&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking">
 * NC21 链表内指定区间反转</a>
 *
 * @author or2
 * @Description 将一个链表\ m m 位置到\ n n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。
 * 例如：
 * 给出的链表为 1\to 2 \to 3 \to 4 \to 5 \to NULL1→2→3→4→5→NULL, m=2,n=4m=2,n=4,
 * 返回 1\to 4\to 3\to 2\to 5\to NULL1→4→3→2→5→NULL.
 * 注意：
 * 给出的 mm,nn 满足以下条件：
 * 1 \leq m \leq n \leq 链表长度1≤m≤n≤链表长度
 * @create 2021年09月06日 时间: 11:22
 */
public class ReverseBetween {

    private static class ListNode {
        int val;
        ListNode next = null;
    }

    /**
     * @param head ListNode类
     * @param m    int整型
     * @param n    int整型
     * @return ListNode类
     */
    public ListNode reverseBetween(ListNode head, int m, int n) {
//        添加头结点, (牛客网默认有参构造)
        ListNode headAux = new ListNode();
        headAux.next = head;
//        定位区间, 找到第 m 个结点 (后面便是原链表的第 m 个结点)
        ListNode pNode = headAux;
        for (int i = 0; i < m - 1; i++) {
            pNode = pNode.next;
        }
        ListNode mNode = pNode;
//        找到原链表第 n 个结点
        for (int i = m - 1; i < n; i++) {
            pNode = pNode.next;
        }
        ListNode nNode = pNode;
//        使用头插法逆序链表
        while (mNode.next != nNode) {
            ListNode node = mNode.next;
            mNode.next = node.next;
            node.next = nNode.next;
            nNode.next = node;
        }

        return headAux.next;
    }
}
